
#ifndef _ARBOLBMAS_H_
#define _ARBOLBMAS_H_

#include "../Comunes/Clave.h"
#include "../Comunes/RegistroArbol.h"
#include "../Comunes/CadenaBytes.h"
#include "NodoInterior.h"
#include "NodoHoja.h"
#include "IteradorArbolBMas.h"
#include "Resultado.h"
#include "../Comunes/Persistor.h"
#include "../Comunes/Constantes.h"
#include "ComparadorClavesContexto.h"

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;


class ArbolBMas {

	friend class Nodo;
	friend class NodoInterior;
	friend class NodoHoja;

private:
	Nodo* raiz;
	int primeraHoja;
	int cantidadNodos;
	int maxTamanioClave;
	int cantidadRegistros;
	vector<int> nodosLibres;
	Persistor* persistor;

public:

	/*
	 * Constructor
	 * Recibe por parametro la ruta del archivo donde se va a guardar la estructura, y el tamanio
	 * maximo de clave que puede almacenar.
	 * Pre:
	 * Pos: Queda creada una instancia de ArbolBMas.
	 * 		Los archivos correspondientes al arbol y a datos de control
	 * 		quedan abiertos y creados si no existieran.
	 */
	ArbolBMas(string ruta_archivo, int maxTamanioClave);

	/*
	 * Destructor
	 */
	~ArbolBMas();

	/*
	 * Primitiva que permite ingresar un dato (registro) a la estructura
	 * Pre: El registro debe existir y ser de tipo Registro. Recibo la clave y el Registro.
	 * Pos: Devuelve TRUE si se inserto correctamente y FALSE en caso contrario.
	 */
	bool insertar(RegistroArbol* registro);

	/*
	 * Primitiva que sirve para modificar un Registro.
	 * Pre: El registro debe existir y ser de tipo Registro. Recibo el Registro.
	 * Pos: Devuelve TRUE si se modifico correctamente y FALSE en caso de que no exista
	 * 		dicho registro dentro del Hash.
	 */
	bool modificar(RegistroArbol* registro);

	/*
	 * Primitiva que devuelve un IteradorArbolBMas al primer nodo hoja del arbol.
	 * Pre:
	 * Pos: Devuelve el iterador en caso de que exista algun registro en el arbol. En caso
	 * 		contrario devuelve NULL.
	 */
	IteradorArbolBMas* begin();

	/*
	 * Primitiva que va a buscar una clave o cadena de caracteres en la estructura o archivo
	 * Pre: Recibo la clave del registro a buscar.
	 * Pos: Si lo encontro, devuelve el registro, sino, devuelve NULL.
	 */
	RegistroArbol* buscar(Clave clave);

	/*
	 * Primitiva que busca una clave y devuelve una lista registros como resultado
	 * Pre: Recibo la clave del registro a buscar.
	 * Pos: Si encuentra resultados devuelve una lista con los mismos, sino devuelve una lista vacia.
	 */
	vector<RegistroArbol*> busquedaMultiple(Clave clave);

	/*
	 * Primitiva que elimina un registro de la estructura.
	 * Pre: Paso la clave del registro a eliminar.
	 * Pos: Devuelve TRUE si se pudo borrar correctamente y FALSE en caso contrario.
	 */
	bool borrar(Clave clave);

	/*
	 * Primitiva que pasa todos los datos de la estructura en un archivo de texto plano
	 * para que pueda ser analizado en una observacion inmediata.
	 * Pre: ruta_archivo debe contener caracteres validos para un nombre de archivo.
	 * Pos: Crea un archivo de texto con los todos los datos de la estructura.
	 */
	void mostrar(string ruta_archivo);

	/*
	 * Primitiva que devuelve un Nodo a partir del numero de nodo pasado por parametro.
	 * Pre: numeroDeNodo debe ser un numero de nodo valido.
	 * Pos: Devuelve un puntero al Nodo buscado. Si el numero de nodo es invalido
	 * 		devuelve NULL.
	 */
	Nodo* leerNodo(int numeroDeNodo);

	int getCantidadBloques();

	int getUltimoIdIngresado();

private:

	/*
	 * Indica si clave1 es menor que clave2.
	 */
	bool claveMenor(Clave clave1, Clave clave2);

	/*
	 * Indica si clave1 es menor o igual que clave2.
	 */
	bool claveMenorIgual(Clave clave1, Clave clave2);

	/*
	 * Indica si clave1 es igual a clave2.
	 */
	bool claveIgual(Clave clave1, Clave clave2);

	/*
	 * Indica si clave1 esta contenida en clave2.
	 */
	bool claveContenida(Clave clave1, Clave clave2);

	/*
	 * Crea una instancia de un NodoHoja.
	 */
	NodoHoja* crearNodoHoja();

	/*
	 * Crea una instancia de un NodoInterior.
	 */
	NodoInterior* crearNodoInterior(int nivel);

	/*
	 * libera la memoria ocupada por unNodo.
	 */
	void liberarMemoriaNodo(Nodo *unNodo);

	/*
	 * Devuelve la posicion en el nodo 'unNodo' de la clave buscada. La primera posicion en el nodo es la cero.
	 * Se usa tanto para busquedas, modificaciones y bajas, como para altas, donde la posicion devuelta es donde
	 * deberia insertarse el nuevo elemento.
	 */
	int obtenerPosicion(Nodo *unNodo, Clave clave);

	/*
	 * Metodo recursivo que se encarga de insertar un elemento en el arbol, y realizar los splits necesarios.
	 * nodoCorriente es el nodo que se esta procesando.
	 * clave y dato corresponden al elemento a insertar.
	 * En clavePromocion se devuelve la clave que se actualiza en el nodo padre.
	 * En nuevoNodo se devuelve el nodo que se genera en el caso de un split.
	 * El metodo devuelve un boolean que indica si se pudo realizar o no la insercion.
	 */
	bool insertarRecursivo(Nodo* nodoCorriente, Clave clave, CadenaBytes dato, Clave* clavePromocion, Nodo** nuevoNodo);

	/*
	 * Se encarga de hacer un split de unNodoHoja, generando un nuevoNodoHoja y la clavePromocion que es la que se actualiza en el
	 * nodo padre.
	 */
	void dividirNodoHoja(NodoHoja* unNodoHoja, Clave* clavePromocion, Nodo** nuevoNodoHoja);

	/*
	 * Se encarga de hacer un split de unNodoInterior, generando un nuevoNodoInterior y la clavePromocion que es la que se actualiza en el
	 * nodo padre.
	 */
	void dividirNodoInterior(NodoInterior* unNodoInterior, Clave* clavePromocion, Nodo** nuevoNodoInterior, int nuevaPosicion);

	/*
	 * Metodo recursivo que se encarga de borrar un elemento del arbol, y realizar los balanceos o fusiones correspondientes.
	 * clave es la clave del elemento a borrar.
	 * nodoCorriente es el nodo que se esta procesado.
	 * nodoIzquierda y nodoDerecha son los nodos que se encuentran al los lados del corriente, NULL en caso de no existir ninguno.
	 * nodoPadreIzquierda y nodoPadreDerecha representan al nodoPadre en la mayoria de los casos, y en los casos en que el nodo en cuestion
	 * se encuentra en alguno de los extremos, representan al padre del padre, segun se encuentre en el extremo izquierdo o derecho.
	 * nodoPadre representa al padre del corriente y posicionPadre la ubicacion del nodoCorriente en el padre.
	 * Puede devolver OK, NO_ENCONTRADO, ACTUALIZAR_ULTIMA_CLAVE o FUSION_NODOS segun sea el caso.
	 */
	Resultado borrarRecursivo(Clave clave, Nodo *nodoCorriente, Nodo *nodoIzquierda, Nodo *nodoDerecha,
			NodoInterior *nodoPadreIzquierda, NodoInterior *nodoPadreDerecha, NodoInterior *nodoPadre, int posicionPadre);

	/*
	 * Se encarga de fusionar dos nodos hoja.
	 * hojaIzquierda y hojaDerecha son los nodos en cuestion. En hoja izquierda se pasan todos los elementos de hojaDerecha.
	 * Devuelve Resultado::FUSION_NODOS.
	 */
	Resultado fusionarHojas(NodoHoja* hojaIzquierda, NodoHoja* hojaDerecha);

	/*
	 * Se encarga de fusionar dos nodos interiores.
	 * nodoIzquierda y nodoDerecha son los nodos en cuestion. En nodoIzquierda se pasan todos los elementos de nodoDerecha.
	 * Si se produce la fusion devuelve Resultado::FUSION_NODOS, sino Resultado::OK
	 */
	Resultado fusionarNodosInteriores(NodoInterior* nodoIzquierda, NodoInterior* nodoDerecha, NodoInterior* nodoPadre, int posicionPadre);

	/*
	 * Se encarga de balancear un nodo hoja derecho, con su izquierdo, pasando elementos a este ultimo.
	 * hojaIzquierda y hojaDerecha son los nodos en cuestion, nodoPadre es el padre de ambos y posicionPadre es la ubicacion en el
	 * padre, del nodo que contiene al elemento a ser borrado.
	 * Si cambia la ultima clave del padre (lo que implicaria cambiar la clave tambien en el padre del padre) se devuelve
	 * Resultado::ACTUALIZAR_ULTIMA_CLAVE, caso contrario se devuelve Resultado::OK
	 */
	Resultado pasarElementosHojaIzquierda(NodoHoja *hojaIzquierda, NodoHoja *hojaDerecha, NodoInterior *nodoPadre, int posicionPadre);

	/*
	 * Se encarga de balancear un nodo interior derecho, con su izquierdo, pasando elementos a este ultimo.
	 * nodoIzquierda y nodoDerecha son los nodos en cuestion, nodoPadre es el padre de ambos y posicionPadre es la ubicacion en el
	 * padre, del nodo actual.
	 */
	void pasarElementosNodoInteriorIzquierdo(NodoInterior *nodoIzquierda, NodoInterior *nodoDerecha, NodoInterior *nodoPadre, int posicionPadre);

	/*
	 * Se encarga de balancear un nodo hoja izquierdo, con su derecho, pasando elementos a este ultimo.
	 * hojaIzquierda y hojaDerecha son los nodos en cuestion, nodoPadre es el padre de ambos y posicionPadre es la ubicacion en el
	 * padre, del nodo que contiene al elemento a ser borrado.
	 */
	void pasarElementosHojaDerecha(NodoHoja *hojaIzquierda, NodoHoja *hojaDerecha, NodoInterior *nodoPadre, int posicionPadre);

	/*
	 * Se encarga de balancear un nodo interior izquierdo, con su derecho, pasando elementos a este ultimo.
	 * nodoIzquierda y nodoDerecha son los nodos en cuestion, nodoPadre es el padre de ambos y posicionPadre es la ubicacion en el
	 * padre, del nodo actual.
	 */
	void pasarElementosNodoInteriorDerecho(NodoInterior *nodoIzquierda, NodoInterior *nodoDerecha, NodoInterior *nodoPadre, int posicionPadre);

	/*
	 * Persiste un nodo en el archivo del arbol b+.
	 */
	void persistirNodo(Nodo* unNodo);

	/*
	 * Hidrata un nodo del archivo del arbol b+, numeroDeNodo multiplicado al tamanio del nodo es el offset en el archivo.
	 */
	Nodo* hidratarNodo(int numeroDeNodo);

	/*
	 * Se encarga de mostrar la estructura del arbol en el stream de salida pasado por parametro. Es un metodo recursivo, unNodo es
	 * el nodo corriente, la tabulacion va cambiando segun el nivel.
	 */
	void mostrarNodo(ofstream& salida, Nodo* unNodo, int tabulacion);

	/*
	 * Devuelve el numero correspondiente a un nuevo nodo. En el caso de que hayan quedado nodos libres se devuelve
	 * un numero de nodo del vector de nodosLibres, en caso contrario se genera un nuevo numero de nodo.
	 */
	int obtenerNumeroDeNodo();

	/*
	 * Persiste el numero de nodo de la primera hoja y el vector de nodos libres en el archivo de configuracion.
	 */
	void persistirDatosConfiguracion();

	/*
	 * Levanta el archivo de configuracion y a partir de el setea la primera hoja y genera el vector de nodosLibres.
	 */
	void hidratarDatosConfiguracion();

};

#endif // _ARBOLBMAS_H_
